The maximal clique enumeration (MCE) problem has numerous applications inbiology, chemistry, sociology, and graph modeling. Though this problem is wellstudied, most current research focuses on finding solutions in large sparsegraphs or very dense graphs, while sacrificing efficiency on the most difficultmedium-density benchmark instances that are representative of data sets oftenencountered in practice. We show that techniques that have been successfullyapplied to the maximum clique problem give significant speed gains over thestate-of-the-art MCE algorithms on these instances. Specifically, we show thata simple greedy pivot selection based on a fixed maximum-degree first orderingof vertices, when combined with bit-parallelism, performs consistently betterthan the theoretical worst-case optimal pivoting of the state-of-the-artalgorithms of Tomita et al. [Theoretical Computer Science, 2006] and Naud\'e[Theoretical Computer Science, 2016]. Experiments show that our algorithm is faster than the worst-case optimalalgorithm of Tomita et al. on 60 out of 74 standard structured and randombenchmark instances: we solve 48 instances 1.2 to 2.2 times faster, and solvethe remaining 12 instances 3.6 to 47.6 times faster. We also see consistentspeed improvements over the algorithm of Naud\'e: solving 61 instances 1.2 to2.4 times faster. To the best of our knowledge, we are the first to achievesuch speed-ups compared to these state-of-the-art algorithms on these standardbenchmarks.
展开▼
